public class LCS {
    // 最长公共子序列II
    // https://www.nowcoder.com/practice/6d29638c85bb4ffd80c020fe244baf11?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page

    public String LCS (String s1, String s2) {
        // write code here
        // 状态表示：dp[i][j]表示s1字符串[0,i]之间的子序列和s2字符串[0,j]之间的
        // 子序列的最长子序列
        // 状态转移方程：根据最后一个位置来推导状态转移方程
        // 如果s1[i] == s2[j]，那么dp[i][j] = dp[i-1][j-1] + s1[i]
        // 如果s1[i] != s2[j]，那么dp[i][j]可能的结果就是s1[0,i-1]之间的子序列和
        // s2[0,j]之间子序列的最长公共子序列以及s1[0,i]之间的子序列和s2[0,j-1]
        // 之间子序列的最长公共子序列,
        // dp[i][j] = dp[i-1][j].length() > dp[i][j-1].length() ? dp[i-1][j] : dp[i][j-1]
        if (s1.length() == 0 || s2.length() == 0) {
            return "-1";
        }
        char[] ch1 = (" " + s1).toCharArray();
        char[] ch2 = (" " + s2).toCharArray();
        String[][] dp = new String[ch1.length][ch2.length];
        // 初始化
        // dp[0][j]表示s1[0,0]之间的子序列和s2[0,j]之间的最长公共子序列，为" "
        // dp[i][0]同样也是
        for (int j = 0; j < ch2.length; j++) {
            dp[0][j] = "";
        }
        for (int i = 0; i < ch1.length; i++) {
            dp[i][0] = "";
        }
        for (int i = 1; i < ch1.length; i++) {
            for (int j = 1; j < ch2.length; j++) {
                if (ch1[i] == ch2[j]) {
                    dp[i][j] = dp[i-1][j-1] + ch1[i];
                } else {
                    dp[i][j] = dp[i-1][j].length() > dp[i][j-1].length()
                            ? dp[i-1][j] : dp[i][j-1];
                }
            }
        }
        return dp[ch1.length-1][ch2.length-1].length() == 0
                ? "-1" : dp[ch1.length-1][ch2.length-1];
    }

    public static void main(String[] args) {
        LCS lcs = new LCS();
        System.out.println(lcs.LCS("1a1a31","1a231"));
    }
}
